1. Field of the Invention
The present invention relates generally to the operation of a cache memory in a data processing system. More particularly, the invention relates to methods and apparatus for making cache block replacement decisions based on a combination of least recently used (LRU) stack distance and data reference frequencies.
2. Description of the Prior Art
In many data processing systems, there is provided between the working store of the central processing unit and the main store, a high speed memory unit which is commonly called a "cache". This unit enables a relatively fast access to a subset of data and instructions which were previously transferred from main storage to the cache, and thus improves the speed of operation of the data processing system. The transfer of operands or instructions between main store and cache is usually effected in fixed-length units which are called "blocks" (sometimes "lines") of information. The selection of blocks for transfer to the cache, and also their location in cache (except for a possible pre-assignment of classes to cache sub-areas) depend on the respective program, the operands used, and the events that happen during program execution.
Cache memory may also be used to store recently accessed blocks from secondary storage media such as disks. This cache memory could be part of main storage or a separate memory between secondary and main storage.
To enable retrieval of information from the cache, (wherever located), a table of tags of block addresses is maintained in a "directory" which is an image of the cache. Each block residing in cache has its tag or address stored in the respective position in the directory. Once the cache is filled-up, new information can only be entered if an old block is deleted or overwritten. Certain procedures are necessary to select blocks as candidates for replacement, and to update the directory after a change of the cache contents.
A number of systems are known in the art which use cache or high speed buffer stores and provide a mechanism for replacement selection and directory updating.
U.S. Pat. No. 4,322,795 to R. E. Lange et al, discloses a cache memory arrangement using a least-recently- used ("LRU") scheme for selecting a cache location in which to store data fetched from main memory upon a cache miss.
U.S. Pat. No. 4,168,541 to C. W. DeKarske, discloses a replacement system for a set associative cache buffer, i.e., a cache which is subdivided into sets each associated with a class of data having some address bits in common. The system uses age bits to determine the least recently used block in a set. The age bits are updated each time a block is referenced. A directory (tag buffer) is provided for storing tags representing a portion of the address bits of data words currently in the cache memory. The patent describes details of updating the directory and the age bits.
Belady et al, in U.S. Pat. No. 3,964,028, discloses a cache utilizing an LRU/stack replacement scheme and teaches the concept of utilizing stack distances as part of the replacement criteria.
Hamstra et al, in U.S. Pat. No. 4,530,054, discloses utilizing linked lists of time stamped access information to manage a cache memory.
Chang, in U.S. Pat. No. 4,458,310, discloses partitioning a cache memory system into a plurality of cache memories, each for storing cache memory words having a similar time usage history. This structure allows lowest priority replacement circuitry to be used when main memory words are transferred to cache.
Two printed publications also illuminate the state of the prior art. The first, entitled "High Performance Computer Architecture", by Harold S. Stone, teaches using a fixed partition directory and reference bits to make replacment choices. The second, entitled "Principles of Database Buffer Management", by Wolfgang Effelsberg and Theo Haerder, teaches using reference counts to make replacement choices.
In general, none of the prior art references discloses making replacement decisions based on a combination of LRU stack distance and data reference frequencies. More particularly, none of the prior art references teach the use of boundaries to determine when reference counts should be incremented and which blocks are eligible for replacement; none teach the use of integer counts to determine when non-LRU choices should be made, nor do any of the references teach the use of a single main directory with arbitrary position boundaries.
It would be desirable to be able to make replacement decisions based on the aforesaid combination of LRU stack distance and data reference frequencies, utilizing reference counts, arbitrary boundaries, etc., to improve cache management performance.